首页 > 试题广场 >

两数之和

[编程题]两数之和
  • 热度指数：401430 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给出一个整型数组 numbers 和一个目标值 target，请在数组中找出两个加起来等于目标值的数的下标，返回的下标按升序排列。
（注：返回的数组下标从1开始算起，保证target一定可以由数组里面2个数字相加得到）

数据范围：，，
要求：空间复杂度 ，时间复杂度
示例1

输入

[3,2,4],6

输出

[2,3]

说明

因为 2+4=6 ，而 2的下标为2 ， 4的下标为3 ，又因为 下标2 < 下标3 ，所以返回[2,3]
示例2

输入

[20,70,110,150],90

输出

[1,2]

说明

20+70=90
算法知识视频讲解
添加回答
JavaScript Node
牛客749976080号头像 牛客749976080号
我觉得使用map的方式跟我的实现没有差别啊 
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param numbers int整型一维数组 
 * @param target int整型 
 * @return int整型一维数组
 */
function twoSum( numbers ,  target ) {
    // write code here
    /**
     * find (target - numbers[idx]) in numbers
    */
    let arr = [0,0]
    for (let i=0; i < numbers.length; i++) {
        let cv = numbers[i]
        if (target < cv) continue // 跳过
        let nT = target - cv
        for (let j = i + 1; j < numbers.length; j++) {
            if (numbers[j] == nT) {
                arr[0] = i + 1
                arr[1] = j + 1
                return arr
            }
        }
    }
    return arr
}
module.exports = {
    twoSum : twoSum
};


编辑于 2023-12-13 09:58:16 回复(0)
JavaScript Node
chainwood头像 chainwood
/**
 * 楼里鱼龙混杂，业务没闭环的很多，满足场景只有个例的很多。抄作业的朋友自行揣摩我这个思路里每行代码用意。
 *
 *
 * @param numbers int整型一维数组
 * @param target int整型
 * @return int整型一维数组
 */
function twoSum( numbers ,  target ) {
    let arr = [];
    let map = new Map();
    for(let i=0;i<numbers.length;i++) {
        if(map.has(target - numbers[i])) {
            arr.push(map.get(target - numbers[i])+1);
            arr.push(i+1);
        } else {
            map.set(numbers[i], i);
        }
    }
    let newArr = [...new Set(arr)];
    arr = arr.sort((a,b) => b - a);
    arr = arr.sort(() => -1);  
    return arr;
}
module.exports = {
    twoSum : twoSum
};
发表于 2023-08-15 15:26:53 回复(1)
JavaScript Node
游人耶头像 游人耶 
function twoSum( numbers ,  target ) {
    // write code here
const map = new Map();
  for (let i = 0; i < numbers.length; i++) {
    const complement = target - numbers[i];
    if (map.has(complement)) {
      return [map.get(complement)+1, i+1];
    }
    map.set(numbers[i], i);
  }
  return [];
}
module.exports = {
    twoSum : twoSum
};

发表于 2023-04-25 17:37:28 回复(0)
JavaScript Node
牛客848877901号头像 牛客848877901号
使用Map来进行解答 
/**
  * 
  * @param numbers int整型一维数组 
  * @param target int整型 
  * @return int整型一维数组
  */
function twoSum( numbers ,  target ) {
    const ans = []; //存放结果
    let map = new Map(); //map初始化
    for(let i=0;i<numbers.length;i++){ //遍历数组
        if(map.has(target - numbers[i])){ //搜索是否存在可以相加为target的数，map.has（key）如果数组中有返回true，如果没有返回false
            ans[0]=map.get(target - numbers[i])+1; //找到后存入ans中
            ans[1]=i+1;
            break;
        }else{
            map.set(numbers[i],i); //如果没找到，存入map中
        }
    }
    return ans;
}
module.exports = {
    twoSum : twoSum
};
一开始我在想如何从map中寻找呢，里面一开始没有存任何numbers[]的数据，但是如果没找到，就把该数据存入map中，那么此时的map相当于另一个numbers，这样key也是正确的。
在map中，将numbers中的key和value的位置调换一下，因为最后ans需要的是numbers中的key，所以这样更方便一些。
在找到合适的数字后，使用break，就可以直接得出结果，不需要再继续循环了，也减少内存消耗。
发表于 2022-09-29 16:12:43 回复(0)
JavaScript Node
w布响丸辣头像 w布响丸辣 
function twoSum( numbers ,  target ) {
    // write code here
    let map = {}
    for(let i=0;i<numbers.length;i++){
        if(numbers[i] in map){
            return [map[numbers[i]],i+1];
        }else{
            map[target - numbers[i]] = i+1;
        }
    }
}

发表于 2022-08-13 22:08:45 回复(0)
JavaScript Node
skrheart头像 skrheart
牛客的数组为啥是从1开始😥 
/**
  * 
  * @param numbers int整型一维数组 
  * @param target int整型 
  * @return int整型一维数组
  */
function twoSum( numbers ,  target ) {
    const map = new Map()
    for(let i = 0;i < numbers.length;i++){
        if(map.get(target - numbers[i]) !== undefined){
            return [map.get(target - numbers[i])+1,i+1]
        }
        map.set(numbers[i],i)
    }
}
module.exports = {
    twoSum : twoSum
};

发表于 2021-10-31 00:15:24 回复(0)
JavaScript Node
美英头像 美英
function twoSum( numbers ,  target ) {
    // write code here
    var list = numbers;
    for(var i=0;i<=list.length;i++){
        for(var j=i+1;j<list.length;j++){
            if(target == list[i]+list[j]){
                 return [i+1,j+1];
            }
        }
    }
}
发表于 2021-08-26 17:00:40 回复(0)
JavaScript Node
牛客203154915号头像 牛客203154915号 
function twoSum( numbers ,  target ) {
    // write code here
    let a
    let b
    numbers.forEach((v,i) => {
         numbers.forEach((val,ind) => {
            if(val + v === target && i !== ind){
                a = i + 1
                b = ind + 1
            }
        })
    })
    return [a,b].sort((ts,cs) => ts - cs )
}

发表于 2021-08-20 14:52:19 回复(0)
JavaScript Node
周欣仪头像 周欣仪
可以利用哈希表来存放两数之差来对数字进行对比。
  1. 定义一个哈希表
  2. 用目标数字减去数字中的数字得到差，去哈希表中查看，是否存在差，如果不存在，则将数组中的数字存放入哈希表
  3. 如果哈希表中存在差，则取出数字的下标。
例如题目中的[3,2,4]  6 执行步骤如下所示：
  1. 6-3=3  哈希表中没有数字3，则将3存入哈希表
  2. 6-2=4 哈希表中没有4，则将2存入哈希表，index为2
  3. 6-4=2 正好哈希表中有数字2，则从哈希表中获得数字2的下标2，和4在数组中的下标+1为3
  4. 因此返回2和3
正式的代码如下所示： 
function twoSum( numbers ,  target ) {
    // write code here
    //定义一个hash表用来存放数据
    var map=new Map()
    //获取数组的长度
     var len=numbers.length
     //遍历数组
     for(var i=0;i<len;i++)
         {
             //将目标数字减去数组中数字，得到差
            var num=target-numbers[i]
            //如果哈希表中没有这个差，将这个数字放进去
            if(!map.has(num))
                {
                    map.set(numbers[i],i+1)
                }
             else{
                 //如果有差，则获取到数字的下标
                 return [map.get(num),i+1]
             }
         }

}



发表于 2021-08-17 17:17:59 回复(2)
JavaScript Node
牛客好运好运🙏头像 牛客好运好运🙏 
function twoSum( numbers ,  target ) {
    // write code here
    var len = numbers.length;
    var result = new Array(2);
    for(var i = 0; i < len; i++){
        for(var j = i+1; j < len; j++){
            if(numbers[i] + numbers[j] == target){
                result[0] = i+1;
                result[1] = j+1;
            }
        }
    }
    return result;
}

编辑于 2021-07-19 19:39:24 回复(3)
JavaScript Node
初见呀头像 初见呀 
 function twoSum( numbers ,  target ) {
    // write code here
    let arr=numbers
    let  map=new Map()
    for(let i=0;i<arr.length;i++){
       console.log(map.has(target-arr[i]),i,map,target-arr[i],target,arr[i])
        if(map.has(target-arr[i])    ){
            return [map.get(target-arr[i])+1,i+1]  //这里有点坑,***
        }
        map.set(arr[i],i)
    }
    
    
}

发表于 2021-07-14 19:53:25 回复(0)
提交观点

问题信息

数组 哈希
难度：
11条回答 78121浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号